JZ62 二叉搜索树的第k个结点

https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a

这题主要就是考察二叉搜索树的中序遍历就是排序后的队列，以及迭代的方式 中序遍历

以后看到搜索二叉树就默念：中序遍历

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // 因为是二叉搜索树，所以就是中序遍历的顺序
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k == 0) return null;
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        while (!stack.isEmpty() || pRoot != null) {
            while (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            // 取得最左的第一个元素
            TreeNode node = stack.pop();
            if (++count == k) return node;
            // 指向右边的节点（就算为空也有 Stack 的内容）
            pRoot = node.right;
        }
        
        return null;
    }
}